package com.LeeCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 最长连续序列
 **/
public class Code128 {
    public static void main(String[] args) {
        int[] nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        int res = new Code128().longestConsecutive1(nums);
        System.out.println(res);
    }

    public int longestConsecutive(int[] nums) {
        // map 保存包含key的最大连续序列长度，并动态更新边界值
        HashMap<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums) {
            // 已经出现过，不再考虑，只考虑维护边界值
            if (!map.containsKey(num)) {
                // 获取包含num-1的最大连续长度
                int pre = map.containsKey(num - 1) ? map.get(num - 1) : 0;
                // 获取包含num+1的最大连续长度
                int pos = map.containsKey(num + 1) ? map.get(num + 1) : 0;

                int len = pre + pos + 1; // 计算包含num的最大连续长度
                map.put(num, len); // 记录
                map.put(num - pre, len); // 更新边界
                map.put(num + pos, len); // 更新边界
            }
        }
        int maxlen = 0;
        for (Integer val : map.values()) {
            if (maxlen < val)
                maxlen = val;
        }
        return maxlen;
    }

    // 官方题解， 使用set去重
    public int longestConsecutive1(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}
